package leetcode.editor.cn;

/**
 * ******************************************************
 *
 *
 *
 * 假设你有一个特殊的键盘，上面只有四个键，它们分别是：
 *
 * 1、A 键：在屏幕上打印一个 A。
 *
 * 2、Ctrl-A 键：选中整个屏幕。
 *
 * 3、Ctrl-C 键：复制选中的区域到缓冲区。
 *
 * 4、Ctrl-V 键：将缓冲区的内容输入到光标所在的屏幕上。
 *
 * 这就和我们平时使用的全选复制粘贴功能完全相同嘛，只不过题目把 Ctrl 的组合键视为了一个键。
 * 现在要求你只能进行 N 次操作，请你计算屏幕上最多能显示多少个 A？
 *
 *
 *
 * @author liugh9
 * @version 1.0
 * @classname _4键键盘
 * @description
 * @date 2023/09/21 16:22
 * <p>
 * ******************************************************
 */
public class _4键键盘 {


    /**
     *
     *
     * 这种思路稍微有点复杂，但是效率高。继续走流程，「选择」还是那 4 个，但是这次我们只定义一个「状态」，也就是剩余的敲击次数 n。
     *
     * 这个算法基于这样一个事实，最优按键序列一定只有两种情况：
     *
     * 要么一直按 A：A,A,...A（当 N 比较小时）。
     *
     * 要么是这么一个形式：A,A,...C-A,C-C,C-V,C-V,...C-V（当 N 比较大时）。
     *
     * 因为字符数量少（N 比较小）时，C-A C-C C-V 这一套操作的代价相对比较高，可能不如一个个按 A；
     * 而当 N 比较大时，后期 C-V 的收获肯定很大。
     * 这种情况下整个操作序列大致是：开头连按几个 A，然后 C-A C-C 组合再接若干 C-V，然后再 C-A C-C 接着若干 C-V，循环下去。
     *
     * 换句话说，最后一次按键要么是 A 要么是 C-V。明确了这一点，可以通过这两种情况来设计算法：
     *
     *
     * int[] dp = new int[N + 1];
     * // 定义：dp[i] 表示 i 次操作后最多能显示多少个 A
     * for (int i = 0; i <= N; i++)
     *     dp[i] = max(
     *             这次按 A 键，
     *             这次按 C-V
     *         )
     * 对于「按 A 键」这种情况，就是状态 i - 1 的屏幕上新增了一个 A 而已，很容易得到结果：
     *
     *
     * // 按 A 键，就比上次多一个 A 而已
     * dp[i] = dp[i - 1] + 1;
     * 但是，如果要按 C-V，还要考虑之前是在哪里 C-A C-C 的。
     *
     * 刚才说了，最优的操作序列一定是 C-A C-C 接着若干 C-V，
     * 所以我们用一个变量 j 作为若干 C-V 的起点。那么 j 之前的 2 个操作就应该是 C-A C-C 了：
     *
     *
     * @param N
     * @return
     */
    public int maxA(int N) {
        int[] dp = new int[N + 1];
        dp[0] = 0;
        for (int i = 1; i <= N; i++) {
            // 按 A 键
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++) {
                // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
                // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }
        // N 次按键之后最多有几个 A？
        return dp[N];
    }

}
